Обзор текущих разработок по материалам EUROMICRO Symposium on Digital Systems Design 2003 Work in Progress Session, Belek (Turkey), September 2003 Долинский М.С. В сентябре 2003 года в Турции был проведена очередная международная конференция "EUROMICRO Symposium on Digital Systems Design 2003". Одна из ее секций (Work in Progress Session) была посвящена "незаконченным" работам исследователей из разных европейских стран. Читательскому вниманию предлагается краткий обзор представленных на этой секции материалов. Polarity Conversion Using Sparse and Partition Technique Napier University, Edinburgh, UK Данная статья представляет вычислительные методы преобразования булевых функций из суммы произведений (SOP-sum of products) в FPRM- (Fixed Polarity Reed-Muller) выражения и наоборот. FPRM представление булевых функций - это XOR от AND-термов, в которых каждая булева переменная появляется либо в прямой, либо в инверсной форме, но не в обоих. В последнее десятилетие синтез схем в базисе AND/XOR привлекает все больший интерес, поскольку он обеспечивает более компактные схемы для определенного класса задач, таких как коррекция ошибок, арифметические преобразования, телекоммуникация. Еще одним достоинством схем, выполненных в базисе AND/XOR, является их отличная тестируемость. Analysis of Replacing Software-based Systems with FPGA and a case Study on a Digital Output IO-Board Malardaren University, Vasteras, Sweden Данная статья анализирует возможности замены программного обеспечения встроенных систем аппаратным на основе FPGA. Поставлены три вопроса: - Какие ограничения определяют проектирование встроенных систем? - Как сравнивать программные решения с аппаратными? - Каких преимуществ можно достичь, заменяя программные решения аппаратными? Основыми ограничениями, которые принимаются во внимание разработчиками при выборе архитектуры и распределении задач между программным и аппаратным являются цена(площадь кристалла), время разработки (время выхода на рынок), производительность, потребление энергии. Как правило, программные решения дешевле аппаратных, имеют более короткий цикл разработки, но менее производительны, чем аппаратные решения. В статье приводится пример замены реальной микроконтроллерной платы сбора данных на 50k FPGA, которая обеспечила удешевление продукции на 30%, уменьшение времени отклика с 200 мс до 20 мс и сокращение времени проектирования на 40%. VcOS: An Operating System supporting Virtual Circuitry University of Rostok, Germany Развитие микроэлектронных технологий привело к возможности динамического реконфигурирования аппаратного обеспечения в целях повышения производительности или сокращения энергопотребления. Для эффективного использования таких возможностей требуются новые операционные системы, которые авторы статьи назвали vcOS (virual circuitry supporting OS). Статья предлагает концепцию такой vcOS. Большинство мультизадачных операционных систем поддерживает управление задачами, планирование, механизмы межзадачного взаимодействия и синхронизации, файловую систему, управление памятью и драйверы. Для динамической реконфигурации аппаратного обеспечения вводится понятие виртуальная схема (virtual circuitry): Прежде всего, в аппаратную платформу в дополнение к традиционным процессору, памяти и периферийным устройствам вводится динамически реконфигурируемая FPGA. Ядро vcOS получает, соответственно, дополнительные функции: размешение и трассировка виртуальных схем, планирование аппаратных задач. Наконец, пользовательское приложение может теперь иметь не только программные, но и аппаратные задачи, задаваемые в двоичном (исполняемые файлы для программного обеспечения и битовые конфигурационные потоки для аппаратного обеспечения) или исходном (С/С++ тексты для программного обеспечения и HDL-тексты для аппаратного обеспечения) коде. В качестве кандидата на развитие до vcOS предлагается Linux, поскольку она распространяется бесплатно вместе с исходными тестами и к тому же хорошо документирована. Partition-based Algorithm for Efficient 2D HW Multitasking Univesidad de Madrid, Spain В работе анализируются способы эффективного использования динамически реконфигурируемой FPGA в мультизадачной vcOS. При этом авторы ведут рассмотрение возникающих проблем на следующем уровне абстракции: - динамически реконфигурируемая FPGA рассматривается как прямоугольник площади W*H - каждая пользовательская аппаратная задача рассматривается как прямоугольник площади Wi*Hi и характеризуется еще временем "прибытия" Ti и длительностью исполнения Di. Указывается, что ранее предпринимались попытки решать задачи такого сорта с произвольным размещением прямоугольников Wi*Hi в прямоугольнике W*H, но это приводит к чрезвычайно сложным в реализации алгоритмам. Другим предложением было просто разделить FPGA на несколько прямоугольников равной площади. К недостаткам такого подхода авторы отнесят неэффективное использование FPGA задачами существенно меньшего размера, чем выделенные части, а также невозможность исполнения аппаратных задач, которым требуется площадь большего размера, нежели размер введенной секции. Авторы предлагают разбить прямоугольник FPGA двумя прямыми (одна - параллельно одной стороне прямоуголькниа, другая - параллельно другой) на 4 неравные части (например, прямоугольник 20*20 делится на прямоугольники 5*5, 5*15, 15*5 и 15*15) и затем приводят алгоритм размещения прибывающих задач на этом множестве "исполняющих полей". Показыватся преимущества такого подхода перед альтернативами. Efficient Hardware Multitasking through space multiplexing in 2D PTR FPGAs Univesidad de Madrid, Spain Предлагается решение в общем случае проблемы оптимального размещения прибывающих аппаратных задач на прямоугольнике FPGA. Сложность приведенного алгоритма оценивается авторами как O(N^2), где N - количество задач, исполняемых на FPGA. Analysis of Square Root Functions Design and Optimization in FPGAs Bogazici University, Turkey Авторы приводят четыре варианта аппаратной реализации функции корень квадратный (SQRT), которые имеют различные характеристики при сравнении по таким параметрам, как производительность, занимаемая площадь, сложность реализации и др. Самый простой способ найти корень квадратный от числа - это определить диапазон возможных значений корня и эффективным способом просканировать этот диапазон в поиске решения. Приведена таблица, показывающая, что авторы смогли на FPGA Xilinx Virtex II достичь повышения производительности от 15 нс до 2 нс на вычисление корня квадратного из заданного 8-битного числа. Implementing a Neural Processor on a Programmable Logic Device Universita di Pavia, Italy Аппаратные реализации нейронных сетей все шире применяются в тех областях, где обучающие наборы данных значительны, и время исполнения соответствующих программ становится неприемлемо велико. Одним из таких аппаратных решений является нейронный процессор Totem(NC3003), разработанный в Universita di Pavia и изготовленный фирмой Neuricam (www.neuricam.com) как ASIC в середине 90-х годов. К особенностям его архитектуры можно отнести: - 32 параллельных MAC (умножение-сложение) устройства с собственной памятью 256*8 битов для хранения весов. Блоки памяти могут также разделяться несколькими процессорами - четыре внешних таблицы, реализованных на SRAM для вычисления функций активации нейронной сети (16-input, 16 output look-up tables) Эта архитектура оптимизирована для исполнения алгоритма обучения RTS (Reactive Tabu Search) - который является существенной альтернативой известному методу обучения нейронных сетей, называемому Back Propagation, поскольку RTS не требует вычисления производных от функции передачи. Авторы указывают, что использование двух процессоров NC3003 обеспечивает создание персептрона с топологией 64-128-64, способного обрабатывать данные за 10 микросекунд. В данной работе авторы описывают перенос архитектуры NC3003 на FPGA с целью упрощения последующего развития и исследований альтернатив. Low Cost FPGA Implemenation of a High Speed Neural Network NTNU, Norway Каждый узел нейронной сети вычисляет сумму произведений входов на соответствующие им веса, затем эта сумма передается на схему сравнения, которая называется функцией активации узла. Авторы указывают, что существует множество реализаций нейронных сетей как ASIC, их же цель - реализовать нейронную сеть на FPGA. Что они и сделали, использовав 10-долларовую FPGA Spartan-3, и создав нейроную сеть с 1024 (16-битными) входами, с 20 узлами. Эта нейронная сеть способна выполнять 4 миллиарда операций в секунду и обрабатывать входной поток данных со скоростью 3 Гигабит/сек. Система распознавания образов, построенная на базе такого нейронного процессора может обрабатывать черно-белые картинки размером 32*32 пиксела со скоростью 200,000 кадров в секунду или может обрабатывать 24-цветные картинки размером 640*480 пикселов со скоростью 150 кадров в секунду. A High Speed ASIC Implementation of the RSA Algorithm Middle East Techical Univesity, Ankara, Turkey Использование электронных устройств в коммерции привело к повышенному вниманию к безопасности данных. Среди систем шифрования данных особую популярность получили системы с открытыми ключами, защита которых основа на трудоемкости факторизации (разложения на множители) больших чисел. Одним из наиболее известных алгоритмов шифрования является алгоритм RSA (Rivest-Shamir-Adleman), который определяется следующим соотношениями: C = X^e mod M для шифрования и X = C^d mod M для дешифрования где X - сообщение C - зашифрованное сообщение e - открытый ключ d - секретный ключ M - модуль Возведение в степень по модулю может быть выполнено как последовательное вычисление произведений по модулю с использованием алгоритма Монтгомери. Но поскольку при увеличении значений размеров обрабатываемых данных (1024 бита и более) вычисления становятся весьма времяемкими, требуются схемы аппаратной реализации алгоритма RSA. Один из вариантов такой схемы приводится в данной статье. Авторы реализовали 1024-битный RSA алгоритм на Xilinx FPGA и добились производительности шифрования 273 Кбит/сек. A 2.41-GB/s ASIC Implementation of the Rijndael Algorithm Middle East Techical Univesity, Ankara, Turkey В октябре 2002 года после трехлетнего анализа возможностей 15 кандидатов, NIST (National Institute of Standards and Technologies, http://csrc.nist.gov) выбрал алгоритм Rijndael в качестве стандарта AES (http://csrc.nist.gov/encryption.aes, Adavanced Encryption Standard) на смену алгоритму DES (Data Encryption Standard), который являлся стандартом с 1977 года. Поэтому авторы реализовали и описывают в данной работе ASIC, которая обеспечивает кодирование/декодирование данных по стандарту AES, при всех возможных комбинациях длин данных и ключа из чисел 128, 192 и 256 бит. В завершение статьи приводится таблица производительности созданной ASIC в зависимости от соотношения размеров ключа и данных. В случае длины данных 256 бит достигается пиковая производительность устройства 2.41 Гбит/сек при всех размерах ключей (128, 192, 256 битов). Configurable Design and Implementation of the Rijndael Algorithm-AES Bogazici University, Turkey Данная FPGA-реализация алгоритма AES работает с данными длиной 128 битов и ключами длиной 128, 192 и 256 битов. Все модули описаны на синтезируемом VHDL. Цель разработки - получить первоначальное представление о возможных производительности и размерах. Дальнейшая разработка позволит создать конфигурируемое пользователем ядро AES-шифрования/ дешифрования в целях оптимизации по производительности, размерам, потребляемой энергии. PICHAFF: A distributed SAT Solver for Microcontrollers University of Freiburg, Germany "SAT-проблема" - NP-полная задача доказательства того, что заданная булева функция может получить значение 1 (и нахождение набора соответствующих значений аргументов) - одна из фундаментальных проблем вычислительной техники. В течение последних лет создано несколько алгоритмов решения этой задачи (например, GRASP, CHAFF, SATO). Эти алгоритмы успешно применяются в таких областях как проверка моделей, доказательства эквивалентности, временной анализ. Однако рост размерностей решаемых задач вызывает к жизни распределенные системы, обеспечивающие сокращение времени решения таких задач за счет параллельных вычислений. Авторы разработали распределенную версию алгоритма CHAFF для сети микроконтроллеров Mirochip PIC17C43. В качестве коммуникационного процессора в системе также задействован процессор Motorola MC68340. Для параллелизации поиска решений все пространство возможных решений разбивается на непересекающеся подмножества и раздается отдельным процессорам. Если какой-то из процессоров заканчивает свою работу, он получает от коммуникационного процессора часть задачи от другого процессора. В статье приводится таблица тестирования созданной системы на множествах тестов DIMACS и PADERBORN EASY. LNA Arithmetic for MPEG Encoding Using a Fast DCT Lehigh University, Bethlehem, USA LNS (Logarithmic Number System) - логарифмическая система счисления - это альтернативный способ представлять числа, в дополнение к наиболее часто применяемым сегодня способам "с фиксированой точкой" и "с плавающей точкой". В LNS число представляется с помощью порядка в определенной базе и знака числа. Тогда умножение двух LNS-чисел это просто сумма их экспонент. Однако сложение таких чисел - это нелинейная операция и она требует использования использования "тадлиц поиска" (look-up tables). Размеры сумматоров для LNS-чисел растут экспоненциально по мере роста длины операндов. Поэтому LNS-числа могут иметь преимущества только для вычислений с невысокой размерностью данных - что характерно для портативных устройств. В статье приводится сравнение выполнения MPEG кодирования, основанного на DCT-преобразовании. Показывается, что при стандартном кодировании чисел в диапазоне от -2048 до 2047 (что требует MPEG-1) требуется 12 битов, в то время как для LNS-кодирования тех же чисел требуется всего 6 битов (1 бит знака числа, 1 бит знака порядка и 4 бита для порядка). Приводится схема аппаратной реализации DCT для LNS-чисел. Показывается, что она в четыре раза более экономична, нежели аналогичная схема для чисел с фиксированной точкой. Утверждается, что LNS может найти применение в портативных видео-камерах с низким потреблением энергии. Dynamically Reconfigurable Coprocessor for Network Processors University of Lubeck, Germany Значительный рост сетей Интернет привел к росту требований к функциональности и производительности таких устройств, как маршрутизаторы и свичи. Сегодня они, как правило, реализуются как ASIC в связи необходимостью высокой производительности обработки пакетов. Однако, ASIC имеют длительный цикл разработки (год и более) и не могут быть адаптированы к изменениям в протоколах или стандартах, которые довольно часто случаются в мире сетевой обработки. Поэтому в последнее время ведутся разрабоки специальных сетевых процессоров (Network Processors, NP). Такие NP не только способны анализировать заголовки пакетов на высокой скорости. Они также способны параллельно решать задачи шифрации/дешифрации и фильтрации пакетов и даже более глубокого анализа пакетов, например, для защиты от вирусов. Сегодня от сетевых процессоров требуется производительность 25-100 миллионов пакетов в секунду при минимальной длине пакета в 40 байтов. Достижение такой производительности возможно только при использовании параллельных архитектур и разгрузке основного процессора за счет переноса части задач на специальные сопроцессоры. Поскольку функции, возлагаемые на сопроцессоры, могут существенно меняться с течением времени, авторы предлагают выполнять сетевые сопроцессоры на базе динамически реконфигурируемых FPGA. При этом предлагается поддерживать два типа реконфигурации: 1) Сетевой сопроцессор реконфигурируется при изменении программного обеспечения сетевого процессора 2) Динамическая реконфигурация сопроцессора по ходу реальной эксплуатации Hardware implementation of Complex Data Processing Algorithms Gomel State University, Belarus Аппаратная реализация сложных алгоритмов, как правило, существенно увеличивает сроки разработки. В то же время, программная реализация таких алгоритмов, существенно сокращая сроки разработки, может не обеспечить требуемой производительности. Поэтому авторами разработан аппаратно-программный комплекс, который позволяет провести разработку и отладку алгоритмов как программного обеспечения, а затем автоматически сгенерировать синтезируемые VHDL-описания, обеспечивающие аппаратную реализацию отлаженных алгоритмов. При этом автоматически проводится максимальное распараллеливание алгоритма и учет ограничений базовой аппаратной платформы. В качестве исходного языка описания алгоритмов выступает CMPDL. CMPDL - это подмножество языка С, обеспечивающее эффективную компиляцию CMPDL-программ в язык ассемблера микропрограммых автоматов. Специальная система синтеза микропрограммных автоматов строит по ассемблерной микропрограмме соответствующие управляющий и операционный автоматы, задаваемые как синтезируемые VHDL-описания. Benchmarking Leon for DSP Applications: A Guide for Algorithm Implementation LEON - это DSP-процессор, который свободно распространяется в синтезируемом VHDL-описании. Авторы проводят анализ эффективности использования процессора LEON в 16-битных DSP-приложениях. Анализ проводился на следующих алгоритмах: корень квадратный, умножение, скалярное произведение, быстрое преобразование Фурье, Хемминогово кодрование, фильтр с конечной импульсной характеристикой (32 точки), конволюция (32 точки) и тоногенерация. Заключение Анализ тематики текущих исследований, представленных на ЕвроМикро 2003 в секции текуших разработок, показывает, что в сфере интересов исследователей находятся специальные архитектуры (шифрование/дешифрование, сетевая обработка, DSP-обработка, нейронные сети и нейропроцессоры, FPRM-выражения, LNS-числа в DSP-обработке), которые могут обеспечивать все более возрастающие потребности в производительности. Альтернативный способ повышения производительности - создание систем параллельной обработки. К сожалению, в обоих случаях (специальные процессоры и параллельные архитектуры) серьезным препятствием на пути разработчиков становится недопустимо длительный цикл разработки. Поэтому в фокусе исследований оказываются системы, которые позволяют автоматизировать процесс разделения задач на программные и аппаратные подзадачи, а также развитие операционных систем, которые до сих пор управляли только программными задачами, возможностями управления аппаратными задачами (виртуальными схемами).